package cn.cxq.learning.array;

import java.util.HashMap;

/**
 * 牛客题霸-全部题目
 * 数组中只出现一次的数（其它数出现k次）
 * 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 256M，其他语言512M 热度指数：3052
 * 本题知识点： 位运算
 *  算法知识视频讲解
 * 题目描述
 * 给定一个整型数组 arrarr 和一个整数 k(k>1)k(k>1)。
 * 已知 arrarr 中只有 1 个数出现一次，其他的数都出现 kk 次。
 * 请返回只出现了 1 次的数。
 * 示例1
 * 输入
 * 复制
 * [5,4,1,1,5,1,5],3
 * 返回值
 * 复制
 * 4
 */
public class FoundOnceNumber {

    // 使用HashMap解决：
//    public int foundOnceNumber (int[] arr, int k) {
//        // write code here
//        HashMap<Integer,Integer> map = new HashMap<>();
//
//        for(int i = 0; i < arr.length; i++) {
//            if (map.get(arr[i]) == null) {
//                map.put(arr[i], 1);
//            } else {
//                map.put(arr[i], map.get(arr[i]) + 1);
//            }
//        }
//
//        int result = 0;
//
//        //最后剩下一个长度为一的map
//        for (int key : map.keySet()) {
//            if (map.get(key) == 1) {
//                result = key;
//                break;
//            }
//        }
//
//        return result;
//    }

    // 位运算思路：
    // 出现k次就不能再用异或的方法了，因为k(奇数)个相同的数异或还是得到本身。
    // 但是还是可以采用位运算的思想，因为出现k(奇数)次的数字每个位（0或者1）也是出现k(奇数)次，
    // 因此可以每一位的和能够被k整除（对k取余为0）。所以如果把每个数的二进制表示的每一位加起来，
    // 对于每一位的和，如果能被k整除，那对应那个只出现一次的数字的那一位就是0，否则对应的那一位是1。
    public int foundOnceNumber (int[] arr, int k) {

        int[] bitSum = new int[32];

        for (int i = 0; i < 32; i++) {
            int sum = 0;

            for(int num : arr) {
                sum += num >> i & 1;
            }

            bitSum[i] = sum;
        }

        int res = 0;

        for (int i = 0; i < 32; i++) {
            if (bitSum[i] % k != 0) {
                res += 1 << i;
            }
        }

        return res;
    }

}
